Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
Лабораторна робота №9
з дисципліни
«Комп’ютерна графіка»
на тему:
“ ПРОСТИЙ АЛГОРИТМ ЗАПОВНЕННЯ З ЗАПАЛОМ”.
Львів – 2008
Мета: Ознайомлення з основами комп‘ютерної графіки.
Теоретичні основи.
Використовуючи стек, можна розробити простий алгоритм заповнення гранично-визначеної області. Стек - це просто масив чи інша структура даних, в яку можна послідовно поміщати значення і з якої їх можна послідовно виймати. Коли нові значення додаються чи поміщаються в стек, всі інші значення опускаються вниз на один рівень. Коли значення виймаються чи видаляються із стека, інші значення спливають чи піднімаються нагору на один рівень. Такий стек називається стеком прямої дії чи стеком з порядком обслуговування "першим прийшов, останнім вийшов" (FILO). Простий алгоритм заповнення з запалом можна представити в наступному вигляді:
Простий алгоритм заповнення з запалом і стеком
Помістити затравочний піксел у стек
Поки стек не порожній
Витягти піксел зі стека
Привласнити пікселу необхідне значення
Для кожного із сусідніх до біжучого 4-зв’язних пікселів перевірити: чи є він граничним пікселом чи не привласнене пікселу необхідне значення. Проігнорувати піксел у кожнім з цих двох випадків. В іншому випадку помістити піксел у стек.
Алгоритм можна модифікувати для 8-зв'язних областей, якщо переглядати 8-связні піксели, а не тільки 4-зв'язні. Наведемо більш формальний виклад алгоритму, у якому передбачається існування затравочного піксела і гранично-визначеної області.
Простий алгоритм заповнення.
Запал (х, у) видає затравочний піксел
Push - процедура, що поміщає піксел у стек
Pop - процедура, що витягає піксел зі стека
Піксел (х, у) = Запал (х, у)
Ініціалізуємо стек
Push Піксел (х, у)
While (стек не порожній)
Вибираємо піксел зі стека
Pop Піксел (х, у)
If Піксел(х, у)<>Нове_значення then
Піксел(х, у)=Нове_значення
End if
Перевіримо, чи треба поміщати сусідні піксели в стек
If (Піксел(х+1, у)<>Нове_значення and
Піксел(х+1, у)<>Гран_значення) Then
Push Піксел(х+1, у)
If (Піксел(х, у+1)<>Нове_значення and
Піксел(х, у+1)<>Гран_значення) Then
Push Піксел(х, у+1)
If (Піксел(х-1, у)<>Нове_значення and
Піксел(х-1, у)<>Гран_значення) Then
Push Піксел(х-1, у)
If (Піксел(х, у-1)<>Нове_значення and
Піксел(х, у-1)<>Гран_значення) Then
Push Піксел(х, у-1)
End if
End while
В алгоритмі перевіряються і поміщаються в стек 4-зв’язні піксели, починаючи з правого від поточного піксела. Напрямок обходу пікселів - проти годинникової стрілки.
Порядковий алгоритм заповнення з запалом
Запал (х, у) видає затравочний піксел
Pop - процедура, що витягає піксел зі стека
Push - процедура, що поміщає піксел у стек
Ініціалізуємо стек
Push Запал(х, у)
While (стек не порожній)
Вибираємо піксел зі стека і привласнюємо йому нове значення
Pop Піксел(х, у)
Піксел(х, у)=Нове_значення
Зберігаємо х-координату затравочного піксела
ТимЧас_х=х
Заповнюємо інтервал праворуч від запалу
х=х+1
while Піксел(х, у)<>Гран_значення
Піксел(х, у)=Нове_значення
х=х+1
end while
зберігаємо крайній праворуч піксел
Хправ=х-1
Відновлюємо х-координату запалу
х=ТимЧас_х
заповнюємо інтервал ліворуч від запалу
х=х-1
While Піксел(х, у)<>Гран_значення
Піксел(х, у)=Нове_значення
х=х-1
end while
зберігаємо крайній ліворуч піксел
Хлів=х+1
Відновлюємо х-координату запалу
х=ТимЧас_х
перевіримо, що рядок вище не є ні границею багатокутника, ні вже цілком заповнений; якщо це не так, то знайти запал, починаючи з лівого краю підінтервала скануючого рядка.
х=Хлів
у=у+1
while х ? Хправ
шукаємо запал на рядку вище
Прапор=0
While (Піксел(х, у)<>Гран_значення and
Піксел(х, у)<>Нове_значення and х<Хправ
If Прапор=0 then Прапор=1
х=х+1
end while
поміщаємо в стек крайній правий піксел
if Прапор=1 then
if (х=Хправ and Піксел(х, у)<>Гран_значення
and Піксел(х, у)<>Нове_значення) then
Push Піксел(х, у)
Else
Push Піксел(х-1, у)
End if
Прапор=0
End if
Продовжимо перевірку, якщо інтервал був перерваний
Хвх...
